Exercici 7 (Tasca 3).
(pumping lemma,
diagonalization,
hard exercise)
Aproximacions de nombres reals
Donat un nombre real r\in [0,1), sigui L_r \subseteq \{0,1\}^* el llenguatge consistent en els mots no buits w, on w coincideix amb els primers |w| dígits de l’expansió binària de r. Per exemple,
- 1/2 en binari és .1 i, per tant, L_{1/2}=\{1, 10, 100, 1000, \dots\}
- 1/3 en binari és .01010101\dots i, per tant, L_{1/3}=\{0, 01, 010,0101,01010, \dots\}
- Demostreu que L_r és un llenguatge regular si i només si r és un nombre racional.
- Argumenteu per què per a gairebé tots els nombres reals r\in [0,1), L_r no és un llenguatge regular.